The length of a minimal synchronizing word and the \v{C}erny conjecture

摘要

A word w of letters on edges of underlying graph Gamma of deterministicfinite automaton (DFA) is called the synchronizing word if w sends all statesof the automaton to a unique state. J. \v{C}erny discovered in 1964 a sequenceof n-state complete DFA possessing a minimal synchronizing word of length(n-1)^2. The hypothesis, well known today as the \v{C}erny conjecture, claimsthat it is also precise upper bound on the length of such a word for a completeDFA. This simple-looking conjecture is arguably the most fascinating andlongstanding open problem in the combinatorial theory of finite automata. An attempt to prove the \v{C}erny conjecture is wrong.